package leetcode;
import java.util.Deque;
import java.util.List;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
public class leetcode2104子数范围求和 {
	// 没法 回溯 啊  这 真的 不太 好 搞 但是 可以用 直接 用  for循环 来暴力 啊
	/**
	 * 最重要的 作用是  熟悉 滑动 窗口 的使用
	 * 作用 使用 滑动数组的 求出 starrt ~ end 之间的 最大值和最小值的 差值  
	 * 这需要 你维护 两个 队列 用来记录 最大值和最小值的  两个队列
	 * @param start
	 * @param end
	 * @param nums
	 * @return
	 */
		public static int maxAndMinSubValue(int start,int end,int nums[]) {
			Deque<Integer> max = new ArrayDeque<>(); 
			Deque<Integer> min =new ArrayDeque<>();
			for(int i = start; i <= end;i++) {
				while(!max.isEmpty() && nums[max.peekLast()] <= nums[i]) {
					max.removeLast();
				}
				// 添加的是索引   这样的好处 不言而喻 对吧 很多 方便之处  
				max.addLast(i);
				while(!min.isEmpty() && nums[min.peekLast()]>=nums[i]) {
					min.removeLast();
				}
				min.addLast(i);
			}
			
//			return Arrays.asList(max.peekFirst(),min.peekFirst());
			return nums[max.peekFirst()] - nums[min.peekFirst()];
		}
		
		// 处理过程      
		public static int process(int index,int []nums,Deque<Integer> path,int len) {
			if(index == len-1) {
				return 0;
//			maxAndMinSubValue();
		}
			int sum=0;
			/**
			 * 子数组 要求的 是 连续的 所以  不能跳着 只能 连续 的话 这样 倒是可以 保证连续
			 *注意横向 只 遍历 一次 这样 还有必要 用 for 循环嘛？？  没有 必要了啊 
			 */
			for(int i = index; i <= index+1; i++) {
				path.add(index);
				System.out.println(path);
				sum+=maxAndMinSubValue(path.peekFirst(),path.peekLast()+1,nums);
				process(index+1,nums,path,len);
				path.removeLast();
			}
			return sum;
}
		public static void main(String []args) {
			int nums[] = {1,2,3};
			Deque<Integer> path = new ArrayDeque<>();
			int ans = process(0,nums,path,nums.length);
			System.out.println(ans);
			System.out.println(maxAndMinSubValue(0,nums.length-1,nums));
		}
}